package org.tony.algorithms;

public class MinHeap
{
	private int[]	data;
	private int		heapSize;

	public MinHeap(int[] data)
	{
		this.data = data;
		this.heapSize = data.length;
	}

	public void minHeapfy(int index)
	{
		int lIndex = left(index);
		int rIndex = right(index);
		int smallest;
		if (lIndex < heapSize && data[lIndex] < data[index])
		{
			smallest = lIndex;
		}
		else
		{
			smallest = index;
		}

		if (rIndex < heapSize && data[rIndex] < data[smallest])
		{
			smallest = rIndex;
		}
		if (smallest != index)
		{
			int temp = data[index];
			data[index] = data[smallest];
			data[smallest] = temp;
			minHeapfy(smallest);
		}
	}

	public void buildHeap()
	{
		int length = data.length;
		for (int i = length / 2 - 1; i >= 0; i--)
		{
			minHeapfy(i);
		}
	}

	public int left(int index)
	{
		return index * 2 + 1;
	}

	public int right(int index)
	{
		return index * 2 + 2;
	}

	public void print()
	{
		for (int i : data)
		{
			System.out.print(i + " ");
		}
	}

	public static void main(String[] args)
	{
		int[] a = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
		MinHeap mh = new MinHeap(a);
		mh.buildHeap();
		mh.print();
	}
}
